﻿#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;

class Solution {
private:
    static const int maxn = 1001;
    vector<int> postOrder;
    int dp[maxn][maxn];
    bool dfs(int left, int right) {
        if (left >= right - 1) return true;
        if (dp[left][right] >= 0) return dp[left][right];
        int cRoot = postOrder[right - 1];
        int split = right - 1;
        bool greater = false;
        for (int p = left; p < right; p++) {
            if (!greater && postOrder[p] > cRoot) {
                split = p;
                greater = true;
            }
            if (greater && postOrder[p] < cRoot) {
                return dp[left][right] = false;
            }
        }
        return dp[left][right] = (dfs(left, split) && dfs(split, right - 1));
    }
public:
    bool verifyPostorder(vector<int>& postorder) {
        this->postOrder = postorder;
        memset(dp, -1, sizeof(dp));
        return dfs(0, postOrder.size());
    }
};

Solution solution;

int main() {
    vector<int> postorder = { 1,3,2,6,5 };
    auto ans = solution.verifyPostorder(postorder);
    cout << ans << endl;
    return 0;
}